/*
实验6-5 对顶堆维护中位数
分数 30
作者 陈越
单位 浙江大学

设需要维护一个可重集合，支持的操作有：初始化集合、向集合中插入一个元素、查询集合的中位数（若有偶数个元素，则中位数为排序后中间两数的均值）、销毁集合。试利用对顶堆的思想，写出上述四种操作的实现。
函数接口定义：

void InitSet(Set set, int capacity);  // 初始化容量为capacity的集合set
void Insert(Set set, ElemSet x);      // 将元素x插入集合set
double GetMedian(Set set);            // 获取set的中位数
void DestroySet(Set set);             // 销毁set

其中 Set 相关的数据类型的定义如下：

typedef int ElemSet; // 集合元素值为整型
typedef struct SetNode *Set;
struct SetNode {
    MaxHeap small;  // 存储较小一半数据的最大堆
    MinHeap large;  // 存储较大一半数据的最小堆
};

其中最大堆和最小堆结构定义为：

typedef ElemSet HElemSet;
typedef int Position; // 数组下标即为元素位置
typedef struct BinaryHeapNode *MaxHeap;
typedef struct BinaryHeapNode *MinHeap;
typedef struct BinaryHeapNode *Heap;
struct BinaryHeapNode {
    HElemSet *data;  // 数据元素数组
    int size;        // 规模
    int capacity;    // 容量
};

两种堆分别定义了一套操作，以下函数可以直接调用：

void InitPQueue(Heap h, int capacity);     // 初始化堆
void DestroyPQueue(Heap h);                // 销毁堆
void InsertMaxHeap(MaxHeap h, HElemSet x); // 插入最大堆
HElemSet ExtractMax(MaxHeap h);            // 最大堆取顶
void InsertMinHeap(MinHeap h, HElemSet x); // 插入最小堆
HElemSet ExtractMin(MinHeap h);            // 最小堆取顶

裁判主函数首先创建一个 SetNode 结构体，并读入总容量 capacity；调用 InitSet
初始化一个空集合；随后读入一系列指令并执行。指令分为插入（格式为 I
x）和查询中值（格式为 Q），分别对应对 Insert 和 GetMedian 的调用（每个 Q
对应一个输出）。当输入结束后，调用 DestroySet 销毁集合。
简单起见，插入时不需要考虑溢出问题，即测试数据保证插入的元素个数不超过给定容量；查询中位数时不需要考虑集合为空的情况，即测试数据保证不会要求查询空集。

输入样例：

10
8
I 1 Q I 4 Q I 2 Q I 8 Q

输出样例：

1.0
2.5
2.0
3.0
*/

#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 集合元素值为整型 */

/* 堆的定义 - 对应函数由裁判实现，细节略 */
typedef ElemSet HElemSet;
typedef int Position; /* 数组下标即为元素位置 */
typedef struct BinaryHeapNode *MaxHeap;
typedef struct BinaryHeapNode *MinHeap;
typedef struct BinaryHeapNode *Heap;
struct BinaryHeapNode {
    HElemSet *data; /* 数据元素数组 */
    int size;       /* 规模 */
    int capacity;   /* 容量 */
};
void InitPQueue(Heap h, int capacity); /* 初始化堆 */
void DestroyPQueue(Heap h);            /* 销毁堆 */
void SiftUpMax(MaxHeap h, Position i);
void SiftDownMax(MaxHeap h, Position i);
void InsertMaxHeap(MaxHeap h, HElemSet x); /* 插入最大堆 */
HElemSet ExtractMax(MaxHeap h);            /* 最大堆取顶 */
void SiftUpMin(MinHeap h, Position i);
void SiftDownMin(MinHeap h, Position i);
void InsertMinHeap(MinHeap h, HElemSet x); /* 插入最小堆 */
HElemSet ExtractMin(MinHeap h);            /* 最小堆取顶 */
/* 堆的定义结束 */

/* 对顶堆的定义 */
typedef struct SetNode *Set;
struct SetNode {
    MaxHeap small; /* 存储较小一半数据的最大堆 */
    MinHeap large; /* 存储较大一半数据的最小堆 */
};
void InitSet(Set set, int capacity); /* 初始化容量为capacity的集合set */
void Insert(Set set, ElemSet x);     /* 将元素x插入集合set */
double GetMedian(Set set);           /* 获取set的中位数 */
void DestroySet(Set set);            /* 销毁set */
/* 对顶堆的定义 结束 */

int main(void) {
    Set set;
    int capacity, n, i;
    char cmd;
    ElemSet x;

    set = (Set)malloc(sizeof(struct SetNode));
    scanf("%d\n", &capacity);
    InitSet(set, capacity);
    scanf("%d\n", &n);
    for (i = 0; i < n; i++) {
        scanf("%c ", &cmd);
        if (cmd == 'I') { /* 执行插入 */
            scanf("%d ", &x);
            Insert(set, x);
        } else { /* 执行查询中值 */
            printf("%.1f\n", GetMedian(set));
        }
    }
    DestroySet(set);
    return 0;
}
/* 你的代码将被嵌在这里 */

/* 初始化容量为capacity的集合set */
void InitSet(Set set, int capacity) {
    set->small = (MaxHeap)malloc(sizeof(struct BinaryHeapNode));
    set->large = (MinHeap)malloc(sizeof(struct BinaryHeapNode));
    InitPQueue(set->small, capacity);
    InitPQueue(set->large, capacity);
}

/* 将元素x插入集合set */
void Insert(Set set, ElemSet x) {
    if (set->small->size == 0) {
        InsertMaxHeap(set->small, x);
    } else {
        // 没有获取堆顶元素的函数，只能先取出再插入
        ElemSet m = ExtractMax(set->small);
        InsertMaxHeap(set->small, m);
        if (x <= m) {
            InsertMaxHeap(set->small, x);
        } else {
            InsertMinHeap(set->large, x);
        }
    }
    if (set->small->size > set->large->size + 1) {
        InsertMinHeap(set->large, ExtractMax(set->small));
    } else if (set->large->size > set->small->size) {
        InsertMaxHeap(set->small, ExtractMin(set->large));
    }
}

/* 获取set的中位数 */
double GetMedian(Set set) {
    double m = 0;
    if (set->small->size == set->large->size) {
        // 没有获取堆顶元素的函数，只能先取出再插入
        ElemSet max = ExtractMax(set->small);
        InsertMaxHeap(set->small, max);
        ElemSet min = ExtractMin(set->large);
        InsertMinHeap(set->large, min);
        m = (max + min) / 2.0;
    } else if (set->small->size > set->large->size) {
        ElemSet max = ExtractMax(set->small);
        InsertMaxHeap(set->small, max);
        m = max;
    } else {
        ElemSet min = ExtractMin(set->large);
        InsertMinHeap(set->large, min);
        m = min;
    }
    return m;
}

/* 销毁set */
void DestroySet(Set set) {
    DestroyPQueue(set->small);
    DestroyPQueue(set->large);
    free(set);
}